On this page you can get a detailed analysis of a word or phrase, produced by the best artificial intelligence technology to date:
геометрия
двусвязный
общая лексика
двусвязный
Двусвязный список рёбер (англ. doubly connected edge list) другое название — полурёберная структура данных (англ. half-edge data structure) — это структура данных, которая представляет планарный граф на плоскости или многогранник в пространстве. Эта структура обеспечивает эффективную работу с топологической информацией, связанной с рассматриваемыми объектами (вершинами, рёбрами, гранями). Её часто применяют в различных алгоритмах вычислительной геометрии для обработки разбиений плоскости на многоугольники, таких как планарный линейный граф. Например, диаграмму Вороного обычно представляют в виде DCEL внутри ограничивающего прямоугольника.
Эту структуру данных впервые предложили Мюллер и Препарата для представления выпуклого многогранника.
Позже распространение получили изменённые варианты структуры, но название осталось.
Изначально структура создавалась для представления связных графов, однако DCEL можно использовать и для представления несвязных графов.